#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// K个一组翻转链表
class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        // 1. 先求出需要逆序多少组
        ListNode *cur = head;
        int n = 0;
        while (cur)
        {
            cur = cur->next;
            n++;
        }
        n /= k;

        ListNode *newHead = new ListNode();
        ListNode *tail = newHead;
        cur = head;
        // 2. 重复 n 次：⻓度为 k 的链表的逆序即可
        for (int i = 0; i < n; i++)
        {
            // 标记头插的前驱节点
            ListNode *tmp = cur;
            for (int j = 0; j < k; j++)
            {
                ListNode *next = cur->next;
                cur->next = tail->next;
                tail->next = cur;
                cur = next;
            }
            // 更新下一次的前驱节点
            tail = tmp;
        }

        // 把不需要翻转的接上
        tail->next = cur;
        cur = newHead->next;
        delete newHead;
        return cur;
    }
};

// 盛最多水的容器
class Solution
{
public:
    int maxArea(vector<int> &height)
    {
        int n = height.size(), ans = 0;
        int left = 0, right = n - 1;
        while (left < right)
        {
            ans = max(ans, min(height[left], height[right]) * (right - left));
            if (height[left] <= height[right])
            {
                left++;
            }
            else
                right--;
        }

        return ans;
    }
};

// 字符串转整数
class Solution
{
public:
    int myAtoi(string s)
    {
        long long int ans = 0;
        int flag = 1, i = 0;
        while (s[i] == ' ')
            i++;
        if (s[i] == '-')
        {
            flag = -1;
            i++;
        }
        else if (s[i] == '+')
            i++;
        while (s[i] >= '0' && s[i] <= '9')
        {
            if (ans > INT_MAX / 10 || (ans == INT_MAX / 10 && s[i] > '7'))
            {
                return flag > 0 ? INT_MAX : INT_MIN;
            }
            ans = ans * 10 + s[i] - '0';
            i++;
        }
        return ans * flag;
    }
};

// 数组中第K个最大元素
class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        priority_queue<int, vector<int>, greater<int>> q;
        for (auto x : nums)
        {
            q.push(x);
            if (q.size() > k)
                q.pop();
        }

        return q.top();
    }
};

class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        srand(time(nullptr));
        return qsort(nums, 0, nums.size() - 1, k);
    }

    int qsort(vector<int> &nums, int l, int r, int k)
    {
        if (l == r)
            return nums[l];

        int key = getRandom(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (nums[i] < key)
                std::swap(nums[++left], nums[i++]);
            else if (nums[i] == key)
                i++;
            else
                std::swap(nums[i], nums[--right]);
        }

        // [l,left] [left + 1,right - 1] [right,r]
        //  a             b              c
        int c = r - right + 1, b = right - left - 1;
        if (c >= k)
            return qsort(nums, right, r, k);
        else if (b + c >= k)
            return key;
        else
            return qsort(nums, l, left, k - c - b);
    }

    int getRandom(vector<int> &nums, int left, int right)
    {
        int r = rand();
        return nums[left + r % (right - left + 1)];
    }
};

// 下一个排列
class Solution
{
public:
    void nextPermutation(vector<int> &nums)
    {
        int n = nums.size();
        // 找到前面一个较小的数字,后面一个较大的数字
        // 进行交换,然后将较大数右边的数需要按照升序重新排列
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = n - 1; j > i; j--)
            {
                if (nums[i] < nums[j])
                {
                    swap(nums[i], nums[j]);
                    sort(nums.begin() + i + 1, nums.end());
                    return;
                }
            }
        }
        // 没有找到后小前大的数,则说明是最大数了，则排序即可
        sort(nums.begin(), nums.end());
    }
};
